﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.BacktrackingCode
{
    //组合问题
    class Combination
    {
        //=====================================================力扣77 组合
        //给定两个整数n和k，返回范围[1,n]中所有可能的k个数的组合
        List<IList<int>> result;// 存放符合条件结果的集合
        List<int> path;// 用来存放符合条件结果
        public IList<IList<int>> Combine(int n, int k)
        {
            result = new List<IList<int>>();
            path = new List<int>();
            BackTracking(n, k, 1);
            return result;
        }
        void BackTracking(int n, int k, int startIndex)
        {
            if(path.Count == k)
            {
                result.Add(new List<int>(path));
                return;
            }
            for (int i = startIndex; i <= n; i++)
            //for (int i = startIndex; i <= n - (k - path.Count) + 1; i++) ;//剪枝优化
            {
                path.Add(i);// 处理节点 
                BackTracking(n, k, i + 1);// 递归
                path.RemoveAt(path.Count - 1);// 回溯，撤销处理的节点
            }
        }

        //================================================力扣39 组合总和
        //给定一个无重复元素的正整数数组candidates和一个正整数target，找出candidates中所有可以使数字和为目标数target的唯一组合
        //candidates中的数字可以无限制重复被选取，如果至少一个所选数字数量不同，则两种组合是唯一的。
        //对于给定的输入，保证和为target的唯一组合数少于150个
        //1 <= candidates[i] <= 200

        public IList<IList<int>> ComninationSum(int[] candidates, int target)
        {
            result = new List<IList<int>>();
            path = new List<int>();
            Array.Sort(candidates);
            BackTracking_3(candidates, target, 0,0);
            return result;
        }
        void BackTracking_3(int[] candidates, int target, int total,int startIndex)
        {
            if (total == target)
            {
                result.Add(new List<int>(path));
                return;
            }

            //如果total + candidates[i] > target就终止循环， 排序+剪枝操作
            for (int i = startIndex; i<candidates.Length && total + candidates[i] <= target;i++)
            {
                path.Add(candidates[i]);
                total += candidates[i];
                BackTracking_3(candidates, target, total,i);
                total -= candidates[i];
                path.RemoveAt(path.Count - 1);
            }
        }

        //================================================力扣40 组合总和2
        //给定一个数组candidates和一个目标数target,找出candidates中所有可以使数字和为target的组合
        //candidates中每个数字在每个组合中只能使用一次
        //1 <= candidates[i] <= 50
        //candidates中可能有重复
        //解集不能包含重复的组合。
        public IList<IList<int>> CombinationSum2(int[] candidates, int target)
        {//需要去重的话，是对同一树层上去重，同一树枝上都是一个组合的元素，不用去重
            result = new List<IList<int>>();
            path = new List<int>();
            Array.Sort(candidates);//树层去重的话 需要排序
            Backtracking_5(candidates, target, 0, 0);
            return result;
        }
        void BackTracking_4(int[] candidates, int target, int startIndex, int total, bool[] used)
        {
            if(total == target)
            {
                result.Add(new List<int>(path));
                return;
            }

            //判断去重：如果candidates[i] == candidates[i-1] && used[i-1] == false;
            //就说明前一个树枝，使用了candidates[i-1],也就是说同一树层使用过candidates[i-1]
            for(int i = startIndex;i<candidates.Length && total + candidates[i] <= target;i++)
            {
                //used[i-1] == true,说明同一树枝candidates[i-1]使用过
                //used[i-1] == false,说明同一树层candidates[i-1]使用过
                if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false)
                    continue;

                total += candidates[i];
                path.Add(candidates[i]);
                used[i] = (true);
                BackTracking_4(candidates, target, i + 1, total, used);// 和39.组合总和的区别1：这里是i+1，每个数字在每个组合中只能使用一次
                used[i] = false;
                total -= candidates[i];
                path.RemoveAt(path.Count - 1);
            }
        }
        //----------------------------------------------------------
        void Backtracking_5(int[] candidates, int target, int startIndex,int total)
        {
            if(total == target)
            {
                result.Add(new List<int>(path));
                return;
            }

            for(int i = startIndex;i<candidates.Length && total + candidates[i] <= target;i++)
            {
                //要对同一层树层使用过的元素进行跳过
                if (i > startIndex && candidates[i] == candidates[i - 1])
                    continue;

                total += candidates[i];
                path.Add(candidates[i]);
                Backtracking_5(candidates, target, i + 1, total);
                total -= candidates[i];
                path.RemoveAt(path.Count - 1);
            }
        }


        //================================================力扣216 组合总和3
        //找出所有相加之和为n的k个数的组合，组合中只允许含有1-9的正整数，并且每种组合中不存在重复的数字
        public IList<IList<int>> CombinationSum3(int k, int n)
        {
            result = new List<IList<int>>();
            path = new List<int>();
            BackTracking_2(n, k,0, 1);
            return result;
        }
        void BackTracking_2(int n,int k, int total, int startIndex)
        {
            if(path.Count == k)
            {// 如果path.Count == k 但sum != targetSum 直接返回
                if (total == n)
                    result.Add(new List<int>(path));
                return;
            }

            //for (int i = startIndex; i <= 9; i++)
            for (int i = startIndex; i <= 9 - (k-path.Count)+1; i++)//剪枝
            {
                    total += i;// 处理
                path.Add(i);// 处理
                BackTracking_2(n, k, total, i + 1); // 注意i+1调整startIndex
                total -= i;// 回溯
                path.RemoveAt(path.Count - 1);// 回溯
            }
        }

        //========================================================力扣17 电话号码的字母组合
        //给定一个仅包含数组2-9的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。
        //给出数字到字母的映射(与电话按键相同）注意：1不对应任何字母
        List<string> newresult;
        string s;
        string[] letters;
        public IList<string> LetterCombinations(String digits)
        {
            newresult = new List<string>();
            if (digits.Length == 0)
                return newresult;
            s = "";
            letters = new string[10] { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };//0-9对应的字母
            BackTracking_3(digits, 0);
            return newresult;
        }
        void BackTracking_3(string digits, int index)//index是记录遍历第几个数字
        {
            if(index == digits.Length)
            {
                newresult.Add(String.Copy(s));
                return;
            }

            int digit = digits[index] - '0';//将index指向的数字转换为int
            string letter = letters[digit];
            for(int i = 0;i< letter.Length;i++)
            {
                s += letter[i];
                BackTracking_3(digits, index + 1);
                s = s.Remove(s.Length - 1, 1);
            }

        }
    }
}
